package 下一个更大元素I496;

import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.Arrays;

/**
 * @author 谢阳
 * @version 1.8.0_131
 */
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[] res = new int[len1];
        int index = len1 - 1;
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        for (int i = len2 - 1; i >= 0; i--) {
            while (!deque.isEmpty() && deque.peek() < nums2[i]) {
                deque.pop();
            }
            for (int j = len1 - 1; j >= 0; j--) {
                if (nums1[j] == nums2[i]) {
                    if (deque.isEmpty()) {
                        res[j] = -1;
                    } else {
                        res[j] = deque.peek();
                    }
                    index--;
                    break;
                }
            }
            if (index == -1) {
                break;
            }

            deque.push(nums2[i]);
        }
        return res;
    }
}

